package com.wuyong.chapter11;

/**
 * 数组实现并查集 Quick Find
 * 时间复杂度：
 * 判断是否相连 isConnected(int p, int q)  O(1)
 * 连接两个元素 unionElements(int p, int q)  O(n)
 */
public class UnionFind1 implements UF {


    private int[] id;
    public UnionFind1(int size){
        id = new int[size];
        for (int i = 0; i < size; i++) {
            id[i] = i;
        }
    }
    @Override
    public int getSize() {
        return id.length;
    }
    private int find(int p) {
        if (p < 0 || p > id.length)
            throw new IllegalArgumentException("p is illegal");
        return id[p];
    }

    /**
     * 判断两个元素是否相连
     * @param p
     * @param q
     * @return
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并两个元素
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {

        int pId = find(p);
        int qId = find(q);
        if (pId == qId){
            return;
        }
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId)
                id[i] = qId;
        }
    }
}
